package j2024.j202408;

import java.util.Arrays;

public class j0814 {
    /**
     * 面试题 17.16. 按摩师
     * @param nums
     * @return
     */
    public int massage(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        if(n==0){
            return 0;
        }
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }


    /**
     * 213. 打家劫舍 II
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
    }
    public int rob1(int[]nums,int  left,int right){
        if(left>right){
            return  0;
        }
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left]  = nums[left];
        for (int i = left + 1; i <= right; i++) {
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }

    /**
     * 740. 删除并获得点数
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int m = 10001;
        int[] arr = new int[m];
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            arr[nums[i]]+=nums[i];
        }
        int[] f = new int[m];
        int[] g = new int[m];
        f[0] =  arr[0];
        for (int i = 1; i < m; i++) {
            f[i] = g[i-1]+arr[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[m-1],g[m-1]);
    }

    /**
     * LCR 091. 粉刷房子
     * @param costs
     * @return
     */
    public int minCost(int[][] costs) {
        int m =costs.length;
        int[][] dp = new int[m+1][3];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
            dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0])+costs[i-1][2];
        }
        return Math.min(dp[m][0],Math.min(dp[m][1],dp[m][2]));
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp =  new int[n][3];
        dp[0][0]  = -prices[0];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]);
            dp[i][2] = dp[i-1][0]+prices[i];
        }
        return Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2]));
    }
}
